package org.example;

public class Test4 {
    //leetcode 将二叉搜索树转化为排序的双向链表
    //https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/?envType=problem-list-v2&envId=linked-list
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        //nodes数组存放链表的头节点和尾节点
        Node[] nodes = new Node[2];
        dfs(root,nodes);
        //将头节点和尾节点连接起来
        nodes[0].left = nodes[1];
        nodes[1].right = nodes[0];
        return nodes[0];
    }

    private void dfs(Node root,Node[] nodes) {
        if (root == null) return;
        //先处理左子树
        dfs(root.left,nodes);
        //将左子树和root连接起来
        if (nodes[1] != null) {
            nodes[1].right = root;
            root.left = nodes[1];
        }else {
            //如果nodes[1]为空，那么就说明root的左子树为空，那么root就为头节点
            nodes[0] = root;
        }
        //更新尾节点
        nodes[1] = root;
        dfs(root.right,nodes);
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Test4 test4 = new Test4();
        test4.treeToDoublyList(node);
        System.out.println(666);
    }
}
